package neo.aoi.octree;

import java.util.ArrayList;
import java.util.List;

import artofillusion.math.BoundingBox;
import artofillusion.object.TriangleMesh;

/**
 * <code>Octree</code> provides an Octree implementation using TriangleBatch 
 * as triangle data source.<br>
 * There is also some intersection methods to find the desired Octree Node.
 * 
 * @author Lucas Goraieb
 */
public class Octree {

//	private BoundingBox boundingBox;
//
//	private List<Octree> children = new ArrayList<Octree>();
//
//	private List<Integer> triangleData;
//
//	private TriangleMesh.Face[] faces;
//
//	private double res;
//
//	/**
//	 * Octree's public construtor. Use the trianglePerNode parameter to fine
//	 * tune the number of nodes according to the size or triangle count of your
//	 * mesh.
//	 * 
//	 * @param faces
//	 *            TriangleBatch as triangle data source
//	 * @param res
//	 *            Max cube size
//	 */
//	public Octree(TriangleMesh.Face[] faces, double res) {
//		this.res = res;
//		this.faces = faces;
//		BoundingBox bb = new BoundingBox();
//		ArrayList<TriangleBatch> batches = new ArrayList<TriangleBatch>();
//		batches.add(faces);
//		bb.computeFromBatches(batches);
//		float largeSize = bb.xExtent;
//		if (bb.yExtent > largeSize) {
//			largeSize = bb.yExtent;
//		}
//		if (bb.zExtent > largeSize) {
//			largeSize = bb.zExtent;
//		}
//		this.boundingBox = new BoundingBox(bb.getCenter(), largeSize,
//				largeSize, largeSize);
//		this.triangleData = new ArrayList<Integer>();
//		for (int i = 0; i < faces.getTriangleCount(); i++) {
//			this.triangleData.add(i);
//		}
//
//	}
//
//	/*
//	 * Protected octree construtor, for the octree's children.
//	 */
//	protected Octree(Octree parent, BoundingBox bb, List<Integer> tris) {
//		this.boundingBox = bb;
//		this.faces = parent.getBatch();
//		this.res = parent.getTrianglePerNode();
//		this.triangleData = tris;
//	}
//
//	public TriangleBatch getBatch() {
//		return batch;
//	}
//
//	public int getTrianglePerNode() {
//		return trianglePerNode;
//	}
//
//	/**
//	 * Get node's bounding box
//	 * 
//	 * @return node's bounding box
//	 */
//	public BoundingBox getBoundingBox() {
//		return boundingBox;
//	}
//
//	protected List<Integer> getTriangleData() {
//		return triangleData;
//	}
//
//	/*
//	 * Check every triangle for intersection with the Bounding Box.
//	 */
//	private List<Integer> collectTriangles(BoundingBox bb) {
//		List<Integer> triList = new ArrayList<Integer>();
//		for (Integer i : triangleData) {
//			Vector3f[] vertices = new Vector3f[3];
//			batch.getTriangle(i, vertices);
//			if (bb.contains(vertices[0]) && bb.contains(vertices[1])
//					&& bb.contains(vertices[2])) {
//				triList.add(i);
//			}
//		}
//		return triList;
//	}
//
//	/**
//	 * Build the octree. Required, otherwise the octree will be empty.
//	 */
//	public void build() {
//		if (triangleData.size() > trianglePerNode) {
//			subdivide();
//			triangleData = null;
//			System.gc();
//			for (Octree child : children) {
//				child.build();
//			}
//		} else {
//			onRecurseFinished();
//		}
//	}
//
//	/*
//	 * Creates one Child Node based on x,y,z coordinates
//	 */
//	private void newNode(int x, int y, int z) {
//		float extent = boundingBox.xExtent / 2;
//		Vector3f center = new Vector3f();
//		center.x = boundingBox.getCenter().x + (extent * x);
//		center.y = boundingBox.getCenter().y + (extent * y);
//		center.z = boundingBox.getCenter().z + (extent * z);
//		BoundingBox bb = new BoundingBox(center, extent, extent, extent);
//		List<Integer> tris = collectTriangles(bb);
//		if (tris.size() > 0) {
//			children.add(newOctreeNode(bb, tris));
//		}
//	}
//
//	/*
//	 * Subdivide the Octree node into 8 or less
//	 */
//	private void subdivide() {
//		onSubdivide();
//		newNode(-1, -1, -1);
//		newNode(1, -1, -1);
//		newNode(-1, 1, -1);
//		newNode(1, 1, -1);
//		newNode(-1, -1, 1);
//		newNode(1, -1, 1);
//		newNode(-1, 1, 1);
//		newNode(1, 1, 1);
//	}
//
//	/*
//	 * Collects the intersected triangle data
//	 */
//	private boolean intersectHit(List<Integer> tris) {
//		onIntersectHit();
//		if (triangleData != null) {
//			tris.addAll(triangleData);
//			return true;
//		} else {
//			return false;
//		}
//	}
//
//	/**
//	 * Intersect a point with the Octree
//	 * 
//	 * @param point
//	 * @return List of triangle indexes to be used with
//	 *         TriangleBatch.getTriangle
//	 */
//	public List<Integer> intersectPoint(Vector3f point) {
//		onIntersectStart();
//		List<Integer> tris = new ArrayList<Integer>();
//		if (boundingBox.contains(point)) {
//			intersectRecursivePoint(point, tris);
//		}
//		return tris;
//	}
//
//	@SuppressWarnings("unchecked")
//	private void intersectRecursivePoint(Vector3f point, List<Integer> tris) {
//		if (intersectHit(tris))
//			return;
//		for (Octree child : children) {
//			if (child.boundingBox.contains(point)) {
//				child.intersectRecursivePoint(point, tris);
//			}
//		}
//	}
//
//	/**
//	 * Intersect a BoundingBox with the Octree
//	 * 
//	 * @param bb
//	 *            the BoundingBox
//	 * @return List of triangle indexes to be used with
//	 *         TriangleBatch.getTriangle
//	 */
//	public List<Integer> intersectBox(BoundingBox bb) {
//		onIntersectStart();
//		List<Integer> tris = new ArrayList<Integer>();
//		if (boundingBox.intersectsBoundingBox(bb)) {
//			intersectRecursiveBox(bb, tris);
//		}
//		return tris;
//	}
//
//	@SuppressWarnings("unchecked")
//	private void intersectRecursiveBox(BoundingBox bb, List<Integer> tris) {
//		if (intersectHit(tris))
//			return;
//		for (Octree child : children) {
//			if (child.boundingBox.intersectsBoundingBox(bb)) {
//				child.intersectRecursiveBox(bb, tris);
//			}
//		}
//	}
//
//	/**
//	 * Intersect a BoundingSphere with the Octree
//	 * 
//	 * @param bb
//	 *            the BoundingSphere
//	 * @return List of triangle indexes to be used with
//	 *         TriangleBatch.getTriangle
//	 */
//	public List<Integer> intersectSphere(BoundingSphere bs) {
//		onIntersectStart();
//		List<Integer> tris = new ArrayList<Integer>();
//		if (boundingBox.intersectsSphere(bs)) {
//			intersectRecursiveSphere(bs, tris);
//		}
//		return tris;
//	}
//
//	@SuppressWarnings("unchecked")
//	private void intersectRecursiveSphere(BoundingSphere bs, List<Integer> tris) {
//		if (intersectHit(tris))
//			return;
//		for (Octree child : children) {
//			if (child.boundingBox.intersectsSphere(bs)) {
//				child.intersectRecursiveSphere(bs, tris);
//			}
//		}
//	}
//
//	/**
//	 * Intersect a BoundingCapsule with the Octree
//	 * 
//	 * @param bb
//	 *            the BoundingCapsule
//	 * @return List of triangle indexes to be used with
//	 *         TriangleBatch.getTriangle
//	 */
//	public List<Integer> intersectCapsule(BoundingCapsule bc) {
//		onIntersectStart();
//		List<Integer> tris = new ArrayList<Integer>();
//		if (boundingBox.intersectsCapsule(bc)) {
//			intersectRecursiveCapsule(bc, tris);
//		}
//		return tris;
//	}
//
//	@SuppressWarnings("unchecked")
//	private void intersectRecursiveCapsule(BoundingCapsule bc,
//			List<Integer> tris) {
//		if (intersectHit(tris))
//			return;
//		for (Octree child : children) {
//			if (child.boundingBox.intersectsCapsule(bc)) {
//				child.intersectRecursiveCapsule(bc, tris);
//			}
//		}
//	}
//
//	/*
//	 * Methods to be overriten by extended implementations. Use only if needed.
//	 */
//	protected Octree newOctreeNode(BoundingBox bb, List<Integer> tris) {
//		return new Octree(this, bb, tris);
//	}
//
//	protected void onSubdivide() {
//	}
//
//	protected void onRecurseFinished() {
//	}
//
//	protected void onIntersectStart() {
//	}
//
//	protected void onIntersectHit() {
//	}


}
